#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int minimumEffortPath(vector<vector<int>>& heights) {
    int n = heights.size();
    int m = heights[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0x3f3f3f3f));
    dp[0][0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;
    que.emplace(dp[0][0], 0);
    while (!que.empty()) {
        int val = que.top().first;
        int x = que.top().second / m;
        int y = que.top().second % m;
        que.pop();
        if(val > dp[x][y]) continue;
        for (int i = 0; i < 4; i++) {
            int fx = x + dir[i][0];
            int fy = y + dir[i][1];
            if (fx < 0 || fx >= n || fy < 0 || fy >= m) continue;
            int temp = max(dp[x][y], abs(heights[x][y] - heights[fx][fy]));
            if (temp < dp[fx][fy]) {
                dp[fx][fy] = temp;
                que.emplace(temp, fx * m + fy);
            }
        }
    }
    return dp[n - 1][m - 1];
}